package T4LRU缓存;

import java.util.HashMap;
import java.util.Map;
//1.定义node，初始化head，tail，n，cap，map
//2.get：
//3.put:
//4.refresh
//5.delete
public class T4LRU缓存 {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));//返回1
        cache.put(3,3);//淘汰key=2
        System.out.println(cache.get(3));
        cache.put(3,2);
        System.out.println(cache.get(3));
    }
}

class LRUCache {
    //定义node
    public class Node {
        int key;
        int val;
        Node next;
        Node prev;

        Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node head;
    public Node tail;
    public Map<Integer,Node> map;//通过id来关联到节点对象
    public int n;//最大容量
    //初始化
    public LRUCache(int cap) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;tail.prev = head;
        map = new HashMap<>();
        n = cap;
    }
    //获取元素
    public int get(int key) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.val;
        }
        //没找到
        return -1;
    }
    //放元素
    public void put(int key,int value) {
        Node node = null;
        //存在->更新value
        if(map.containsKey(key)) {
            node = map.get(key);  // 修复：确保node变量指向已存在的节点
            node.val = value;
        } else {
            //不存在->看还有空间放吗
            if(n == map.size()) {
                //无空间：删除链表为尾节点+map也删除
                Node del = tail.prev;
                delete(del);
                map.remove(del.key);
            }
            //存入
            node = new Node(key,value);
            map.put(key,node);
        }
        refresh(node);
    }
    //刷新缓存
    public void refresh(Node node) {
        //先删->再放到链表头
        delete(node);

        Node HNext = head.next;

        //放到链表头（保证先连接再断开）   【见图解】
        node.next = HNext;
        HNext.prev = node;
        head.next = node;
        node.prev = head;
    }

    //删除node节点                      【见图解】
    public void delete(Node node) {
        Node Next = node.next;

        //将前节点和next节点相连
        if(node.prev != null) {
            Node Prev = node.prev;
            Prev.next = Next;
            Next.prev = Prev;
        }
    }

}
